from lrex import LrexError
from lrex.spec import Probe

# When binding requests we are walking through entire requests table
# However this is unwanted, so ignore all root requests which are 
# younger than rq.start_time - RQ_TIME_EPSILON

RQ_TIME_EPSILON = 1000000000 # in nanoseconds (1s)

class LrexOutputError(LrexError):
    pass

class LrexNoRequest:
    def __init__(self, event, subsys, index):
        self.event = event
        self.subsys = subsys
        
        self.glue =  self.subsys.glue_fmtstr % (self.subsys.glue, index)
    
    def __str__(self):
        reason = '(no request with %s)' % self.glue
        return str(self.event) + ' ignored ' + reason 

class LrexUnboundRequest:
    def __init__(self, reason, rq):
        self.reason = reason
        self.rq = rq
    
    def __str__(self):
        return '%s unbound (reason: %s)' % (str(self.rq), self.reason) 

class LrexPairingFail:
    def __init__(self, rq, event):
        self.rq = rq
        self.event = event
    
    def __str__(self):
        return "Couldn't form a pair of events for %s for rq %s" % (self.event, self.rq)

class Event:
    name = '' 
    et = 0 # Start or end
    time = 0
    
    def __init__(self):
        self.params = {}
    
    def __repr__(self):
        return '<Trace.Event %s %d>' % (self.name, self.time)
    
    def parse(self, line, spec):
        # Parse line 
        # 
        # Line:
        # {+/-}{name};{time};{param_name:param_value}...
        
        # Parse +/-
        if line[0] == '+':
            self.et = Probe.START
        elif line[0] == '-':
            self.et = Probe.END
        else:
            raise LrexOutputError('Incorrect beginning of line, must be + or -')
                # Split rest of line by semicolons
        line = line[1:]
        L = line.split(';')            
        
        self.name = L[0]
        self.time = int(L[1])
        
        L = L[2:]
        
        # Search for probe specification
        try:
            self.subsys, self.probe = spec.find(self.name)
        except KeyError:
            raise LrexOutputError('Invalide probe name %s' % self.name)
                 
        # Read params
        for param_pair in L:
            name, value = param_pair.split(':')
            
            # Search for param specification
            try:
                param = self.probe.params[name]
            except KeyError:
                pnames = ','.join([p for p in self.probe.params.keys()])
                raise LrexOutputError('Invalide param name %s; valid names are: %s' % (name, pnames))
            
            value = param.read(value)
            
            self.params[name] = value
    
    def __getitem__(self, key):
        return self.params[key]

class EventPair:
    def __init__(self, start, end):
        self.start = start 
        self.end = end
    
    def get_start_time(self):
        return self.start.time
    
    def get_end_time(self):
        return self.end.time
    
    def get_duration(self):
        return self.get_end_time() - self.get_start_time()
    
    def get_name(self):
        return self.start.name

class Request:
    id = 0
    
    @classmethod 
    def generate_id(cls):
        old_id = cls.id
        cls.id += 1
        
        return old_id
    
    def __repr__(self):
        return '<Request %s %d %s>' % (self.subsys.name, self.id, self.get_glue_kv_str())
    
    def __init__(self, subsys):
        self.id = Request.generate_id()
        
        self.subsys = subsys
        self.events = []
        self.pairs = []
        
        # Subrequests list
        self.sub_rq = []
        
        self.conflict_cache = {}
        self.ccache_valid = False
        
        self.is_root = False
    
    def match(self, other_rk_value):
        return self.rk_value == other_rk_value
    
    def add_event(self, event):
        # For END event form a pair        
        if event.et == Probe.END:
            for se in reversed(self.events):
                if se.name == event.name:
                    break
            else:
                raise LrexPairingFail(self, event)
            
            self.pairs.append(EventPair(se, event))
            
        self.events.append(event)
    
    def add_subrq(self, rq):
        self.sub_rq.append(rq)
        
        self.ccache_valid = False
    
    def get_start_time(self):
        return self.events[0].time
    
    def get_end_time(self):
        return self.events[-1].time
    
    def get_glue_kv(self):
        '''Return key, value tuple for glue'''
        glue = self.subsys.glue
        
        return glue, self[glue] 
    
    def get_glue_kv_str(self):
        key, value = self.get_glue_kv()
        fmtstr = self.subsys.glue_fmtstr
        
        return fmtstr % (key, value)
    
    def get_param_values(self, key):
        values = []
        
        for e in self.events:
            if key in e.params:
                values.append(e.params[key])
        
        return set(values)
    
    def __getitem__(self, key):
        values = self.get_param_values(key)
        
        if not values:
            raise KeyError(key)
        elif len(values) > 1:
            raise ValueError('%s more than 1 value for key %s' % (self, key))
        
        return values.pop()
    
    def get(self, key, default=None):
        try:
            return self[key]
        except KeyError:
            return None
    
    def build_conflict_cache(self):
        self.ccache_valid = True
        for srq in self.sub_rq:
            if srq.subsys not in self.conflict_cache:
                self.conflict_cache[srq.subsys] = dict() 
            
            s_key, s_value = srq.get_glue_kv()
            self.conflict_cache[srq.subsys][s_value] = srq
    
    def has_conflicts(self, rq):
        '''We need to resolve conflicts between subrequests 
        when they are bound to requests.
        
        I.e. in biotrace pages in page cache are reusable, so 
        subrequests in page cache may share same glue key value.
        
        So if root request already have subrq with key value, 
        we stop iterating over root request list'''
        
        try:
            key, value = rq.get_glue_kv()
        except:
            return False
        
        if not self.ccache_valid:
            self.build_conflict_cache()
            
        if rq.subsys not in self.conflict_cache:
            # First request, acceptable
            return False 
        
        if value in self.conflict_cache[rq.subsys]:
            conflict_rq = self.conflict_cache[rq.subsys][value]
            print 'RQ %s conflicts with %s' % (rq, conflict_rq)
            
            return True
        
        return False
         

class EventRouter:
    def __init__(self, spec):
        self.spec = spec
        
        self.rq_workset = {}
        
        self.root_requests = []
        
        # dict subsys -> [rq, rq, ...]
        self.all_requests = {}
        
        for subsys in spec.subsystems.values():
            self.rq_workset[subsys] = {}
            self.all_requests[subsys] = []
    
    def find_request(self, event, subsys, do_del = False):
        rq_table = self.rq_workset[subsys]        
        index = event[subsys.glue] 
        
        try:            
            rq = rq_table[index]
            
            if do_del:
                del rq_table[index]
        
            return rq
        except KeyError:
            raise LrexNoRequest(event, subsys, index)
    
    def add_request(self, event, rq):
        if rq.subsys.is_root_subsys:
            self.root_requests.append(rq)
            rq.is_root = True
        
        self.all_requests[rq.subsys].append(rq)
        
        rq_table = self.rq_workset[rq.subsys]
        index = event[rq.subsys.glue]
         
        rq_table[index] = rq
    
    def bind_request(self, rq):
        key = rq.subsys.bind_key
        value = rq[key]
        
        bound = False
        reason = 'no appropriate RRQ'
        
        rrq_list = self.all_requests[rq.subsys.bind_subsys]
        
        rq_time_threshold = (rq.get_start_time() - RQ_TIME_EPSILON)
        
        for rrq in reversed(rrq_list):            
            if rrq.has_conflicts(rq):
                reason = '%s conflicts' % rrq
                break 
            
            try:
                if value in rrq.get_param_values(key):                 
                    # May be bound to multiple subrequests
                    rrq.add_subrq(rq)
                    bound = True
            except KeyError as ke:
                print "Couldn't find key %s for request %s" % (ke, rrq)
            
            if rrq.get_start_time() < rq_time_threshold:
                reason = 'rrq %d is earlier than rq-eps %s' % (rrq.get_start_time(), rq_time_threshold)
                break
        
        if not bound:
            raise LrexUnboundRequest(reason, rq)
    
    def add_event(self, event):
        subsys, probe = self.spec.find(event.name)
        is_root_event = subsys.is_root_event(event)
        is_finish_event = subsys.is_finish_event(event)
        rq = None
        
        try:
            if event.et == Probe.START:            
                if is_root_event:
                    rq = Request(subsys)
                    self.add_request(event, rq)
                else:
                    rq = self.find_request(event, subsys)            
            else:
                # If root event is finished, finish request and delete it from workset
                rq = self.find_request(event, subsys, do_del = is_finish_event)
                
                if is_finish_event and not rq.is_root:
                    self.bind_request(rq)
            
            rq.add_event(event)
            
            print 'Processed event %s for request %s' % (event, rq)
        except LrexNoRequest as mnr:
            print str(mnr)
        except LrexUnboundRequest as mru:
            print str(mru)
        except LrexPairingFail as mpf:
            print str(mpf)
            
            

class Trace:
    def __init__(self, spec, f):
        self.f = f
        self.spec = spec
        
        self.requests = []
        self.events = []
    
    def parse(self):  
        '''Parse and analyse trace from file f (see constructor)
        
        raises LrexOutputError in case of parsing failure'''
        # Ignore first line      
        started = self.f.readline()
        router = EventRouter(self.spec)
        
        # XXX: readlines() uses lists - this will eat memory on large traces
        # Use generator syntax instead
        
        for n, l in enumerate(self.f.readlines()):
            event = Event()
            try:
                event.parse(l, self.spec)
            except LrexOutputError as moe:
                raise LrexOutputError(str(moe) + ' on line %d' % (n + 1))
            
            self.events.append(event)
            router.add_event(event)
        
        self.requests = router.root_requests
        
    def pprint(self):
        # Pretty print
        
        # (indent, rq)
        stack = [(0, rq) for rq in self.requests]
        
        while stack:
            indent, rq = stack.pop(0)
            
            # Extend stack by subrequests
            stack = [(indent + 1, srq) for srq in rq.sub_rq] + stack
            
            if indent == 0:
                print '-' * 4
                
            print '   ' * indent, '%08d' % rq.id, rq.subsys.name, rq.get_start_time(), rq.get_end_time(), rq.get_glue_kv_str()
                